#include <iostream>
#include <algorithm>
using namespace std;

int PartSort(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		std::swap(a[right], a[left]);
	}
	std::swap(a[keyi], a[left]);
	return left;
}
void QuickSort(int* a,int begin,int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

int main()
{
	int a[] = { 3,2,5,8,4,7,6,9 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}